Stack

Stacks are a abstract data type (ADT), implementable with a linked list or an array. The principle is simple. Imagine we stack books on a table, then we take books away — we unstack the ones on the top first. Elements are last-in first-out (LIFO).

Two fundamental operations are pop() and push(). pop() will remove the node that was most recently “pushed” or inserted into the list. push() inserts a node at the head of the list.

Implementation

class Stack { // assuming a proper node definition
	private:
		Node *head;
	public:
		stack() { head = NULL; }
		~stack() { delete head; }
		void push (int d) {
			Node *p = new Node(d, head);
			head = p;
		}
		int pop () {
			if (head == NULL) // could get segfault if this isn't included!
				return -1;
			Node *p = head;
			head = p->getNext();
			int d = p->getData();
			p->setNext(NULL);
			delete p;
			return d;
		}
}

When we push a new node, we should ensure the new pointer points to the previous head and the head pointer points to the new node. Observe that even if the stack is empty, the push method still works. We use a “cascade delete” here.

In memory

In computer memory, stacks are used to store return addresses. In Nios II, the stack register is r27/sp, and the stack grows downwards (i.e., from the initial stack pointer, we decrement to add elements). To push:

addi sp, sp, -4 # allocates space
stw r8, 0(sp)

To pop:

ldw r8, 0(sp)
addi sp, sp, 4 # de-allocates space

We note that push is the analogue of pop. To pop is to give memory back to the computer.

We initialise sp with the address 0x200000 by convention. If not, the assembler will give us the memory location of the stack, i.e., any manipulations we do with the stack will happen, and we don’t need to figure out where it is. But we do need to increment and decrement the stack pointer manually.

Because we need to read and write to the stack, Pulpissimo’s stack is placed on the L2 cache.

Language-specific

C++

In C++, stacks are provided as part of the STL as std::stack<T>. Note that it’s not possible to iterate through a stack.

Useful methods:

• push() adds an element to the top of the structure.
• pop() removes the top element.
• top() accesses the top element.
• empty() checks whether the container’s empty. size() returns the size of the structure.

See also

• Queue, the first-in-first-out equivalent
• Priority queue