Stack data structure

 
###################### 
####    stack     #### 
###################### 
 
an ADT data structure that satisfies the following operations (and computation complexity for each operation) 
 
- push(elem)   in O(1)     # insertion of an element 
- pop()        in O(1)     # retrieval of the last inserted element 
- is_empty()   in O(1)     # tells if it's empty of not 
- size()       in O(1)     # returns the size  # optional 
- peek()       in O(1)     # returns the last inserted element without removal. aka top()  # optional 
 
======>  LIFO  (last-in, first-out) model. 
 
so the actual underlying data structure for implementing a stack can be an array or linked list, etc. 
(hence ADT) 
 
 
 
##################################### 
###    ADT (abstract data type)   ### 
##################################### 
 
in general, data structures like "stack", "queue", "trees", "heap" are called "ADT" because unlike array and linked list, those are defined as a data type/structure that satisfies a set of operations (and computation efficiency requirement for each operation) 
 
 
 
##################################### 
###    necessity of is_empty()    ### 
##################################### 
 
is_empty() is absolutely needed because otherwise pop() will cause so-called underflow. 
when a stack is empty, pop() cannot simply return NULL(zero) because zero can well be a valid element. 
so gotta implement is_empty() explicitly, and perhaps let pop() throw an exception, is a good/safe/sane approach. 
 
 
 
#################################################### 
####   implementation discussion (Array VS LL)   ### 
#################################################### 
 
it's another typical Array VS LL discussion. 
 
         (pros) 
Array  - pop/push can be done fast, as mem space is already allocated. 
LL     - [de]allocation of mem space for a new elem as it comes and goes. efficient. 
         (cons) 
Array  - need to keep track of the last elem. 
       - because we allocate the chunk mem, may waste mem space, or may need to resize when it gets full. 
LL     - each node keeps a pointer which is an overhead. 
 
 
====> pros and cons are essentially the same thing described either positively or negatively. 
====> no absolute right answer, if the number of elements are generally expected within a certain range, then it makes more sense to use array. 
 
 
 
########################################## 
###   implementation  (C++) using LL   ### 
########################################## 
 
we just use a bi-directional LL. (kind of a tradeoff between simplicity and performance) 
(and of course, this is a good example for exercising template) 
 
 
 
------------------------------------------ kstack.h  // to avoid the compile error discussed in cpp_template 
                                                     // writing the member func def inside the header file. 
 
#include <iostream> 
using namespace std; 
 
template <typename N> struct node 

  N data; 
  node* next; 
  node* prev; 
}; 
 
template <typename T> class kstack 

 public: 
 kstack() : size_of_stack(0) {;} 
  void push(T); 
  T pop();                                // assumes is_empty() is called before calling pop() 
  int is_empty(); 
  int getSize(){ return size_of_stack; } 
  T peek() { return tail->data ;}         // assumes is_empty() is called before calling pop() 
 private: 
  int size_of_stack; 
  node<T>* tail; 
}; 
 
template<typename T> void kstack<T>::push(T t) 

  node<T>* tmp = new node<T>; 
  tmp->data = t; 
  tmp->next = 0; 
  tmp->prev = tail; 
 
  if(!tail)            // first elem is a bit special 
    tail = tmp; 
  else{ 
    tail->next = tmp; 
    tail = tmp; 
  } 
  size_of_stack++; 
  cout << "pushed " << tail->data << endl; 

 
template<typename T> int kstack<T>::is_empty() 

  if( size_of_stack > 0) 
    return 0; 
  else 
    return 1; 

 
template<typename T> T kstack<T>::pop() 

  if(is_empty()) 
    return 0;          // this is actually not right as zero can be a valid elem 
                       // so the expectation is, as disccused above,  user always checks is_empty()) before calling pop() 
  else{ 
    size_of_stack--;   // so, if it's size 1, then this becomes zero 
    T rtval = tail->data; 
    tail = tail->prev; 
 
    if(getSize() == 0){ // last elem is a bit special 
      delete tail; 
      tail = 0; 
    }else{ 
      delete tail->next; 
      tail->next = 0; 
    } 
    return rtval; 
  } 

 
---------------------------------------- 
----------------------------------------  // main.cpp 
 
#include <iostream> 
#include "kstack.h" 
using namespace std; 
 
int main() 

  kstack<int> kst; 
 
  kst.push(123); 
  kst.push(456); 
  kst.push(789); 
  kst.push(1111); 
  kst.push(8888); 
 
  while(!kst.is_empty()){ 
    cout << kst.peek() << " : peeked" << endl;     // just a peek 
    cout << kst.getSize() << " : size " << endl;   // checking size 
    cout << kst.pop() << " : popped" << endl;      // actual pop 
  } 
 
  return 0; 

 
------------------------------------------- 
 
 
 
########################## 
####    reference     #### 
########################## 
 
as always, wikipedia is very good. 
 
(ref) 
http://pages.cs.wisc.edu/~siff/CS367/Notes/stacks.html 
http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/data_struct/005.html 
http://en.wikipedia.org/wiki/Stack_(abstract_data_type) 
 

  1. 2014-06-03 00:09:47 |
  2. Category : data_structure
  3. Page View:

Google Ads