STL Veri Yapısı - Stack

Giriş
Kullanmak için şu dosya dahil edilir.

#include<stack>

Sonra stack tanımlanır.

stack<int> mystack;

Container
Kullanılabilecek olan container tipinin şöyle olması gerekir.

The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics:

• back()
• push_back()
• pop_back()

The standard containers std::vector, std::deque and std::list satisfy these requirements.

Varsayılan container tipini dequeue olmasının sebebi şöyle.

With std::list as underlying container each std::stack::push does a memory allocation. Whereas std::deque allocates memory in chunks and can reuse its spare capacity to avoid the memory allocation.

With small elements the storage overhead of list nodes can also become significant. E.g. std::list<int> node size is 24 bytes (on a 64-bit system), with only 4 bytes occupied by the element - at least 83% storage overhead.

push metodu
Eleman eklemen için push metodu çağrılır.

myStack.push(1);

pop metodu
pop() ile de veri yapısından silinir. Aynı anda en üstteki elemanı alma ve silme işini yerine getiren bir metod yoktur.

myStack.pop(); 

top metodu
Bu iki metod beraber kullanılır. top() ile en üstteki elemanın referansı alınır.

int& i = myStack.top();

Diğer Notlar

Stack iterator metodları sağlamaz.  Bu yüzden stack'i dolaşmak normal şartlarda mümkün değil.

container'a erişmek
1. Kalıtım
Açıklaması şöyle.

Stack and queue aren't containers. They are container adaptors. By design they do not expose raw access to the underlying container. But the underlying containers are serializable standard library containers (vector<> and deque<>, by default respectively). And the standard does specify that the implementation expose it as protected members

İsmi c olan bir alan şeklindedir.

Örnek
Şöyle yaparız.

template<class T, class C>
struct MyStack : std::stack<T, C> 
{
  typedef std::stack<T, C> Stack;
  using Stack::Stack;
  using Stack::operator=;
  using Stack::c; // expose as public
};

MyStack.c şeklinde erişebiliriz.

Örnek
Şöyle yaparız.

template <typename... Args>
struct MyStack : std::stack<Args...> {
  using base = std::stack<Args...>;
  using base::base;
  using base::operator=;

  template <typename Ar>
  void serialize(Ar& ar, unsigned /*version*/) { ar & base::c; }
};

2. Yardımcı metodlar

Biraz daha kolay bir yol şöyle. Yardımcı metodlar tanımlarız.

namespace cppx {
  using std::stack;

  namespace hack {
    template< class Item >
    auto container_of (stack<Item> const& st)
      -> typename stack<Item>::container_type const&
    {
      struct Hacked: stack<Item> { using stack<Item>::c; };
      return st.*&Hacked::c;
    }
  }  // namespace hack

  template< class Item >
  auto begin( stack<Item> const& st)
  { return hack::container_of (st).begin(); }

  template< class Item >
  auto end( stack<Item> const& st)
  { return hack::container_of (st).end(); }

}  // namespace cppx   

Şöyle yaparız.

auto main() -> int
{
  using namespace std;

  stack<int> st;
  for( int const x : {3, 1, 4, 1, 5, 9, 2, 6, 5, 4} )
  {
    st.push( x );
  }

  using cppx::begin; using cppx::end;
  for( auto it = begin( st ); it != end( st ); ++it )
  {
    cout << *it << " ";
  }
  cout << endl;
}