簡介

堆疊(Stack)是資料結構的一種,是一種很基本常見的資料結構,首先利用現實生活中的例子來說明,如下圖

img_7378-stack-of-books-q67-303x500    

假設你有一些書把他們疊起來,一層一層的往上疊,所以每次新的書本會放在最上面,而當想要拿取書本的時候,也是從最上面的開始拿。當然現實生活會有可能從中間抽出書本,不過在程式中是不可以的,在程式世界下圖會更貼切。

03_11_stack  

 所以他是一種後進先出(Last-In-First-Out, LIFO)的排程,而在此資料結構中至少會實作兩個操作:

  1. push:將資料放入堆疊頂端
  2. pop:取出堆疊頂端之資料

有時候也會多實作一些額外的操作以方便使用,例如:

  1. peek:看堆疊頂端的資料而不取出。。(註:也有top等不同的用字)
  2. size:取得堆疊的數目。

在實作上一般可以使用陣列或連結串列(LinkedList)兩種方式來實作:

陣列

堆疊建立時即建立一個陣列,並使用一個索引來記錄目前所指到的位址,新增或移除資料時,同步修改索引位址;如果有實作堆疊數目的功能時,這數字正好可做為此索引之用。優點是不用處理指標鏈結建立與移除,缺點是容量超過陣列大小時需要額外處理。

連結串列

用指標將資料串起來,將新的東西不斷接在最後面,而取出時則移除最後面的東西即可。優缺點與陣列相反。

語法

C#

抽象類別

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Stack
{
    abstract class Stack<T>
    {
        public int Count { get; protected set; }
        abstract public void Push(T value);
        abstract public T Pop();
        abstract public T Peek();
    }
}

陣列

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Stack
{
    class ArrayStack<T> : Stack<T>
    {
        private int capacity;
        private T[] array;

        public ArrayStack()
            : this(10240)
        {
        }

        public ArrayStack(int capacity)
        {
            this.capacity = capacity;
            array = new T[capacity];
        }

        public override void Push(T value)
        {
            if (Count == array.Length)
            {
                T[] newArray = new T[array.Length + capacity];
                Array.Copy(array, newArray, array.Length);
                array = newArray;
            }
            array[Count++] = value;
        }

        public override T Pop()
        {
            T value = array[--Count];
            array[Count] = default(T);
            return value;
        }

        public override T Peek()
        {
            return array[Count - 1];
        }
    }
}

連結串列

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Stack
{
    class Node<T>
    {
        public Node<T> Previous { get; internal set; }
        public T Value { get; internal set; }

        public Node(T value)
        {
            Value = value;
        }
    }

    class LinkedListStack<T> : Stack<T>
    {
        private Node<T> last;

        public override void Push(T value)
        {
            Node<T> node = new Node<T>(value);
            node.Previous = last;
            last = node;
            ++Count;
        }

        public override T Pop()
        {
            Node<T> node = last;
            last = last.Previous;
            node.Previous = null;
            --Count;
            return node.Value;
        }

        public override T Peek()
        {
            return last.Value;
        }
    }
}

Java

抽象類別

public abstract class Stack<T> {
	protected int count;
	
    abstract public void push(T value);
    abstract public T pop();
    abstract public T peek();
    
    public int size()
    {
    	return count;
    }
}

陣列

public class ArrayStack<T> extends Stack<T> {

	private int capacity;
    private T[] array;

    public ArrayStack()
    {
    	this(10240);
    }

    @SuppressWarnings("unchecked")
	public ArrayStack(int capacity)
    {
        this.capacity = capacity;
        array = (T[]) new Object[capacity];
    }

	@SuppressWarnings("unchecked")
	@Override
	public void push(T value) {
		// TODO Auto-generated method stub
		if (count == array.length)
        {
			T[] newArray = (T[]) new Object[array.length + capacity];
            System.arraycopy(array, 0, newArray, 0, array.length);
            array = newArray;
        }
        array[count++] = value;
	}

	@Override
	public T pop() {
		// TODO Auto-generated method stub
		T value = array[--count];
        array[count] = null;
        return value;
	}

	@Override
	public T peek() {
		// TODO Auto-generated method stub
		return array[count - 1];
	}

}

連結串列

public class Node<T>
{
	private Node<T> previous;
	private T value;
	
    public Node<T> getPrevious() 
    { 
    	return previous; 
    }
    
    void setPrevious(Node<T> previous) 
    { 
    	this.previous = previous;
    }
    
    public T getValue()
    { 
    	return value;
    }
    
    void setValue(T value) 
    { 
    	this.value = value;
    }

    public Node(T value)
    {
        this.value = value;
    }
}
public class LinkedListStack<T> extends Stack<T> {

	private Node<T> last;
	
	@Override
	public void push(T value) {
		// TODO Auto-generated method stub
		Node<T> node = new Node<T>(value);
        node.setPrevious(last);
        last = node;
        ++count;
	}

	@Override
	public T pop() {
		// TODO Auto-generated method stub
		 Node<T> node = last;
         last = last.getPrevious();
         node.setPrevious(null);
         --count;
         return node.getValue();
	}

	@Override
	public T peek() {
		// TODO Auto-generated method stub
		return last.getValue();
	}

}

C++

抽象類別

#ifndef STACK_H
#define STACK_H


template<typename T>
class Stack
{
    public:
        Stack()
        {
            count = 0;
        }
        int size()
        {
            return count;
        }
        virtual void push(T value) = 0;
        virtual T pop() = 0;
        virtual T top() = 0;
    protected:
        int count;
    private:
};

#endif // STACK_H

陣列

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H

#include <memory.h>
#include "Stack.h"

template<typename T>
class ArrayStack : public Stack<T>
{
    public:
        ArrayStack(int capacity = 10240)
        {
            cap = capacity;
            arrayLength = capacity;
            array = new T[capacity];
        }
        ~ArrayStack()
        {
            delete [] array;
        }
        void push(T value)
        {
            if (Stack<T>::count == arrayLength)
            {
                T* newArray = new T[arrayLength + cap];
                memcpy(newArray, array, arrayLength * sizeof(T));
                arrayLength += cap;
                delete [] array;
                array = newArray;
            }
            array[Stack<T>::count++] = value;
        }

        T pop()
        {
            T value = array[--Stack<T>::count];
            array[Stack<T>::count] = 0;
            return value;
        }

        T top()
        {
            return array[Stack<T>::count];
        }
    protected:
    private:
        int arrayLength;
        int cap;
        T* array;
};

#endif // ARRAYSTACK_H

連結串列

#ifndef LINKEDLISTSTACK_H
#define LINKEDLISTSTACK_H

#include "Stack.h"

template<typename T>
class Node
{
    public:
        Node(T v)
        {
            value = v;
            previous = 0;
        }
        ~Node()
        {
            delete previous;
        }
        Node<T>* previous;
        T value;
    protected:
    private:
};

template<typename T>
class LinkedListStack : public Stack<T>
{
    public:
        ~LinkedListStack()
        {
            delete last;
        }
        void push(T value)
        {
            Node<T>* node = new Node<T>(value);
            node->previous = last;
            last = node;
            ++Stack<T>::count;
        }
        T pop()
        {
            Node<T>* node = last;
            last = last->previous;
            node->previous = 0;
            T value = node->value;
            delete node;
            --Stack<T>::count;
            return value;
        }

        T top()
        {
            return last->value;
        }
    protected:
    private:
        Node<T>* last;
};

#endif // LINKEDLISTSTACK_H

Push和Pop 500000次實測,同時候內建的類別比較

C#
Built-in Stack Push Time: 13ms
Built-in Stack Pop Time: 8ms
LinkedListStack Push Time: 67ms
LinkedListStack Pop Time: 29ms
ArrayStack Push Time: 57ms
ArrayStack Pop Time: 17ms

Java
Built-in Stack Push Time:  48ms
Built-in Stack Pop Time:  108ms
LinkedListStack Push Time:  300ms
LinkedListStack Pop Time:  12ms
ArrayStack Push Time:  54ms
ArrayStack Pop Time:  9ms

C++
Built-in Push Time: 17ms
Built-in Pop Time: 26ms
LinkedListStack Push Time: 61ms
LinkedListStack Pop Time: 33ms
ArrayStack Push Time: 40ms
ArrayStack Pop Time: 8ms

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()