StackをLinked Listを使って実装

自分用メモ。データ構造とちょっとしたコードの例。

Stack

A stack is a last in, first out data structure. There are two main fundamental operation for stack: push and pop. The push operation adds an item to the top of the stack. The pop operation removes an item from the top of stack, and returns the value. We can implement the stack with linked list or array.

Stacks are often used in the computing world. For example, expression evaluation and syntax parsing. Calculators employing reverse Polish notation use a stack structure to hold values. The expression is evaluated from the left to right using a stack.

  1. when encountering an operand: push it
  2. when encountering an operator: pop two operands, evaluate the result and push it

Linked List

A linked list is a data structure which consists of a sequence of nodes. Each of node contains a reference (link) to the next node in the sequence. With linked list, we can implement other common data structures, including stacks, queues, and associative arrays.

For simplicity, I'll talk about a Singly-linked list.

The merit of a linked list is that the list elements can easily be added or removed without reallocation or reorganization of the entire structure because the data items need not be stored continuously in memory. Linked lists allows insertion and removal of nodes at any point in the list, and can do it with a constant number of operatioons.

The demerit of a linked lists is that they don't allow random access to the data. For example, to obtain the last node of the list, we have to scan all of the list elements.

#include <iostream>
#include <tr1/memory> // shared_ptr
#include <stdexcept>

template <class T>
class Stack {
public:
  Stack() {
	size_ = 0;
  };
  ~Stack() {
	while (!empty()) {
	  pop();
	}
  };
  void push (T data) {
	std::tr1::shared_ptr<Element> elem(new Element);
	std::cout << data << "が追加されました(" << size_ << ")" << std::endl;
	elem->data = data;
	elem->next = head;
	head = elem;
	size_++;
  };
  T pop() {
	if (empty()) throw std::runtime_error("no item in stack");
	T data;
	data = head->data;
	head = head->next;
	size_--;
	return data;
  };
  bool empty() {
	return size_ == 0;
  }
private:
  int size_;
  typedef struct Element {
	struct std::tr1::shared_ptr<Element> next;
	T data;
  };
  std::tr1::shared_ptr<Element> head;
};

int main(int argc, char **argv) {
  Stack<int> stack;

  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  
  while (!stack.empty()) {
	std::cout << stack.pop() << "がpopされました" << std::endl;
  }

  return 0;
};