Fandom

Programmer's Wiki

Stack

407pages on
this wiki
Add New Page
Talk0 Share

A stack is a last-in-first-out list data structure. That is, the last item inserted in the list would be the first item to be retrieved in the list. The "inverse" of a stack is a queue.

To understand this structure, imagine twenty plates stacked together. The most obvious way to retrieve a plate is to pluck (pop) it off the top; to add a plate you would probably lift (push) it to the top. By doing otherwise you would risk making several plates fall to the floor and shatter. (This metaphor is based on the Tower of Hanoi, a common puzzle game.)

Common operations are:

  • push - adds an item to the top.
  • pop - removes and returns the top item.

Less common operations are:

  • count - number of items in the stack
  • peek - retrieves the next item in the stack without removing it from the stack.

Stack structureEdit

A simple stack can be implemented using nodes with the linked list structure.

Creation of a stackEdit

A new empty stack without using sentinel nodes:

node* top = null; // where top represents the last item in the stack

Pushing an itemEdit

newnode is allocation for a new node.

int x;
// assign a value to x
node* new = newnode(x);
if(top==null) {
   *top = new;
}
else {
   top->next = new;
   *top = new;
}

Popping the stackEdit

free is deallocation for the node.

int return_value;
if(top==null) {
   // stack underflow
}
else {
   return_value = top->value;
   node* t = top;
   top = top->next;
   free(t);
}

External linksEdit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.